package com.leetcode.offer.chapter5;

/**
 * @author Dennis Li
 * @date 2020/7/17 22:09
 */
public class ReversePairs_51 {

    /*public int reversePairs(int[] nums) {
        int len = nums.length;
        // 长度为1的数组没有逆序对
        if (len < 2) return 0;
        // 需要询问是否可以改变原始数组
        int[] copy = new int[len];
        System.arraycopy(nums, 0, copy, 0, len);

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) return 0;
        int mid = left + ((right - left) >> 1);
        // 都是左闭右闭的区间
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        int res = leftPairs + rightPairs;
        if (nums[mid] <= nums[mid + 1]) return res;

        int cross = merge(nums, left, mid, right, temp);
        return cross + res;
    }

    // 用一个全局数组来进行拷贝
    private int merge(int[] nums, int left, int mid, int right, int[] temp) {
        // 将元素拷贝到辅助数组
        if (right + 1 - left >= 0)
            System.arraycopy(nums, left, temp, left, right + 1 - left);
        int i = left, j = mid + 1;
        int count = 0;
        for (int k = left; k <= right; k++) {
            // i超界的时候
            if (i == mid + 1) {
                nums[k] = temp[j++];
                //j超界的时候
            } else if (j == right + 1) {
                nums[k] = temp[i++];
            } else if (temp[i] <= temp[j]) { // 小的先放，从小到大
                // <= 原因：要保证j每次放的时候，一定是放的较小的数，这样才一定会产生逆序对
                // 而相等的数就由i进行放置
                nums[k] = temp[i++];
            } else {
                nums[k] = temp[j++];
                count += mid - i + 1;
            }
        }
        return count;
    }
*/

    static class Solution {
        public int reversePairs(int[] nums) {
            if (nums == null || nums.length == 0)
                return 0;
            int len = nums.length;
            return getPairs(nums, 0, len - 1, new int[len]);
        }

        public int getPairs(int[] nums, int lo, int hi, int[] aux) {
            if (lo >= hi) {
                return 0;
            }
            int mid = lo + (hi - lo) / 2;

            int low = getPairs(nums, lo, mid, aux);
            int high = getPairs(nums, mid + 1, hi, aux);

            return low + high + merge(nums, lo, mid, hi, aux);
        }

        private int merge(int[] nums, int lo, int mid, int hi, int[] aux) {
            int i = lo, j = mid + 1, count = 0;

            System.arraycopy(nums, lo, aux, lo, hi - lo + 1);

            for (int k = lo; k <= hi; k++) {
                if (i > mid)
                    nums[k] = aux[j++];
                else if (j > hi)
                    nums[k] = aux[i++];
                else if (aux[i] == aux[j])
                    nums[k] = aux[i++];
                else if (aux[i] > aux[j]) {
                    // j 在右边，当产生了逆序对，由于归并后的部分有序性
                    // 因此比i序号大的都比i更大，因此j和mid - i + 1个数都是逆序
                    count += mid - i + 1;
                    nums[k] = aux[j++];
                } else {
                    nums[k] = aux[i++];
                }
            }
            return count;
        }

    }

}
